1937. Противопожарная безопасность

В городе Х имеется n домов. Некоторые из них соединены между собой односторонними дорогами.

В последнее время в Х участились пожары. Для решения этой проблемы жители решили построить в городе несколько пожарных депо. Однако возникла сложность: пожарная машина, выезжая на вызов, может игнорировать направление дорог, но при возвращении обязана строго соблюдать правила дорожного движения (жители Х неукоснительно их придерживаются!).

Необходимо обеспечить, чтобы пожарная машина, независимо от места её нахождения, всегда могла вернуться в то же депо, из которого она выехала. Поскольку строительство депо является дорогостоящим, городской совет принял решение построить минимально возможное их количество, удовлетворяющее данному условию. Кроме того, в целях экономии пожарные депо могут быть построены только рядом с уже существующими домами.

Напишите программу, определяющую оптимальное размещение пожарных депо.

Вход. В первой строке задано количество  домов n (1 ≤ n ≤ 3000).

Во второй строке указано  количество дорог m (1 ≤ m ≤ 10⁵).

В каждой из последующих m строк описывается дорога в формате a_i b_i, что означает возможность проезда по i-й дороге от дома a_i к дому b_i (1 ≤ a_i, b_i ≤ n).

Выход. В первой строке выведите минимальное количество k пожарных депо, которые необходимо построить. Во второй строке выведите k чисел в любом порядке – номера домов, рядом с которыми следует построить депо.

Если существует несколько оптимальных решений, выведите любое из них.

Пример входа	Пример выхода
5 7 1 2 2 3 3 1 2 1 2 3 3 4 2 5	2 4 5

РЕШЕНИЕ

графы – сильная связность

Анализ алгоритма

В задаче требуется найти минимальное множество вершин графа, достижимое из всех остальных вершин. Для этого рассмотрим конденсацию графа. Обратим внимание на компоненты сильной связности, из которых не выходит ни одного ребра.

Если в такой компоненте не построить пожарную станцию, то пожарная машина, прибывшая из другой компоненты, сможет потушить пожар, однако вернуться обратно, следуя направлениям дорог, уже не сможет. Следовательно, в каждой компоненте сильной связности без исходящих рёбер необходимо построить хотя бы одну пожарную станцию.

Строить дополнительные станции не требуется, поскольку из любой вершины графа существует путь по рёбрам в одну из компонент без исходящих рёбер.

Пример

Входной граф содержит три компоненты сильной связности. Из компонент, состоящих из одной вершины (4 и 5), не выходит ни одного ребра. Следовательно, достаточно построить пожарные станции именно в этих компонентах.

Реализация алгоритма

Входной граф храним в списке смежности g. Обратный граф (граф, в котором направления всех рёбер инвертированы) храним в списке смежности gr.

vector<vector<int> > g, gr;

vector<int> used, top, color, repr;

Функция dfs1 реализует  поиск  в глубину на входном графе. В массиве top сохраняем порядок вершин, соответствующий моменту завершения их обработки при обходе в глубину.

void dfs1(int v)

{

used[v] = 1;

for (int to : g[v])

if (!used[to]) dfs1(to);

top.push_back(v);

}

Функция dfs2 реализует поиск в глубину на обратном графе. Все вершины, посещённые в результате рекурсивных вызовов dfs2, принадлежат одной компоненте сильной связности. Все такие вершины окрашиваются цветом c. Вершины, находящиеся в одной компоненте сильной связности, имеют одинаковый цвет.

Для каждого цвета c в массиве repr сохраняется представитель соответствующей компоненты – любой номер вершины, окрашенной этим цветом.

void dfs2(int v, int c)

{

color[v] = c;

repr[c] = v;

for (int to : gr[v])

if (color[to] == -1) dfs2(to, c);

}

Основная часть программы. Читаем входные данные. Строим обратный граф.

scanf("%d %d", &n, &m);

g.resize(n + 1);

gr.resize(n + 1);

for (i = 0; i < m; i++)

{

scanf("%d %d", &a, &b);

g[a].push_back(b);

gr[b].push_back(a);

}

Запускаем поиск в глубину на исходном графе. Порядок, в котором завершается обработка вершин, сохраняем в массиве top.

used.resize(n+1);

for (i = 1; i <= n; i++)

if (!used[i]) dfs1(i);

Запускаем поиск в глубину на обратном графе. Вершины обратного графа обрабатываются в порядке, заданном в массиве top, при этом обход выполняется справа налево – от конца массива к началу. Для удобства дальнейшей обработки массив top предварительно разворачиваем.

color.assign(n+1, -1);

repr.assign(n+1, -1);

reverse(top.begin(), top.end());

Вершины, принадлежащие одной компоненте сильной связности, окрашиваются одним и тем же цветом. Текущий цвет хранится в переменной c.

c = 0;

for (int v : top)

if (color[v] == -1) dfs2(v, c++);

Переменная c содержит количество компонент сильной связности.

used.assign(c, 1);

for (i = 1; i < g.size(); i++)

for (int to : g[i])

Перебираем все ребра графа (i, to) и проверяем, принадлежат ли вершины i и to разным компонентам сильной связности. Это определяется по разным цветам вершин. Если вершины находятся в разных компонентах, в компоненте с цветом color[i] нет необходимости строить пожарную станцию, поэтому устанавливаем used[color[i]] = 0.

if (color[i] != color[to]) used[color[i]] = 0;

}

Подсчитаем количество компонент c, в которых следует построить пожарную станцию.

c = 0;

for (i = 0; i < used.size(); i++)

if (used[i]) c++;

Выводим минимальное необходимое число пожарных станций.

printf("%d\n",c);

Для каждой компоненты с цветом i, из которой не выходит ни одного ребра, выводим её представителя (значение repr[i]). Именно эти номера домов указывают, возле которых следует построить пожарные станции.

for (i = 0; i < used.size(); i++)

if (used[i]) printf("%d ",repr[i]);

printf("\n");